<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>金矿或者背包问题</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="金矿或者背包问题">金矿或者背包问题</h1>
<h1 id="1-金矿或者背包数目有限一般只有1个不是无限的">1. 金矿或者背包数目有限，一般只有1个，不是无限的。</h1>
<h2 id="11-挖金矿">1.1 挖金矿</h2>
<ul>
<li>(1) 小灰的书 chapter 5.11</li>
<li>(2) <a href="https://blog.csdn.net/weixin_43271086/article/details/90582383">https://blog.csdn.net/weixin_43271086/article/details/90582383</a></li>
</ul>
<p>问题：有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同（情况如下图）</p>
<pre><code>(1) 400 5
(2) 500 5
(3) 200 3
(4) 300 4
(5) 350 3
现在有10个工人, 最多能得到多少个金子
</code></pre>
<pre><code><code><div>#
from functools import lru_cache

# &lt;1&gt;从上到下， 时间复杂度 O(2^n)  n是金矿数目
def golddigger1(gold, people, w):
    ''' gold digger top-&gt;down'''
    if len(gold) == 0 or w == 0:
        return 0
    if people[-1] &gt; w:
        return golddigger1(gold[:-1], people[:-1], w)
    else:
        return max(
            golddigger1(gold[:-1], people[:-1], w),
            golddigger1(gold[:-1], people[:-1], w - people[-1]) + gold[-1]
            )

# &lt;2&gt;从上到下， 时间复杂度 O(2^n)  n是金矿数目, 加入了cache
def golddigger2(gold, people, w):
    ''' gold digger top-&gt;down with memo'''

    @lru_cache(None)
    def _helper(pos, w):
        if pos == -1 or w == 0:
            return 0
        if people[pos] &gt; w:
            return _helper(pos-1,  w)
        else:
            return max(
                _helper(pos-1,  w),
                _helper(pos-1,  w - people[pos]) + gold[pos]
                )
    return _helper(len(gold)-1, w)

# &lt;3&gt;从低向上， 时间复杂度 O(mn), n是金矿数目，m是工人数目， 空间复杂度O(mn)
def golddigger3(gold, people, w):
    ''' dp, from bottom to up'''
    m = len(gold)
    n = w
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if j &lt; people[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-people[i-1]]+gold[i-1] )

    return dp[m][n]

# &lt;4&gt;从低向上， 时间复杂度 O(mn), n是金矿数目，m是工人数目， 空间复杂度O(m)
def golddigger4(gold, people, w):
    ''' dp, from bottom to up'''
    m = len(gold)
    n = w
    dp = [0] * (n+1)
    for i in range(1, m+1):
        for j in range(n, 0, -1): # 一定要从右往左扫描
            if j &lt; people[i-1]:
                dp[j] = dp[j]
            else:
                dp[j] = max(dp[j], dp[j-people[i-1]]+gold[i-1] )

    return dp[n]


def test1():
    gold = [400,500,200,300,350]
    people = [5,5,3,4,3]
    r = golddigger1(gold, people, 10)
    print(f&quot;r={r}&quot;)

def test2():
    gold = [400,500,200,300,350]
    people = [5,5,3,4,3]
    r2 = golddigger2(gold, people, 10)
    print(f&quot;r2={r2}&quot;)

def test3():
    gold = [400,500,200,300,350]
    people = [5,5,3,4,3]
    r3 = golddigger3(gold, people, 10)
    print(f&quot;r3={r3}&quot;) 

def test4():
    gold = [400,500,200,300,350]
    people = [5,5,3,4,3]
    r4 = golddigger4(gold, people, 10)
    print(f&quot;r4={r4}&quot;) 


if __name__ == &quot;__main__&quot;:
    test1()
    test2()
    test3()
    test4()
</div></code></code></pre>
<h1 id="12-背包问题">1.2  背包问题</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=8LusJS5-AGo&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr">https://www.youtube.com/watch?v=8LusJS5-AGo&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr</a></li>
</ul>
<p>上面的挖金矿问题等同于背包问题，有4个盒子，每个盒子的 价值/重量 ， 你的最大负重7， 最多能背多少价值的东西。</p>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp1.png" alt="dp1.png"></p>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp1b.png" alt="dp1b.png"></p>
<h1 id="2-金矿或者背包数目无限">2 金矿或者背包数目无限</h1>
<p>类似于换硬币的问题了。</p>
<pre><code><code><div>
我最开始的想法不是上面这种思路，也是动态规划。 而是记录在i个人情况下，单个金矿能挖到的最大值。 
在gold = [400,500,200,300,350], people=[5,5,3,4,3]的情况下
3个工人能得到的单个金矿最大值是350
4个工人能得到的单个金矿最大值是350
5个工人能得到的单个金矿最大值是500

代码像下面这样
def golddigger5(gold, people, w):
    dic = {}
    for g,p in zip(gold, people):  # 这里有第一个错误， 4个工人情况下能得到的单个金矿最大值是300,而不是350
        if p in dic:
            if dic[p] &lt; g:
                dic[p] = g
        else:
            dic[p] = g

    uniq_people = set(people)

    n = w
    dp = [0] * (n+1)
    for i in range(1, n+1):
        for uniq_p in uniq_people:
            if i &gt;= uniq_p:
                dp[i] = max(dp[i], dp[i-uniq_p] + dic[uniq_p])
    print(dp)
    return dp[n]
这里返回的结果是1050， 而不是正确答案的900，  关键问题是 这道题每个金矿只能选一次！ 不能重复选， 如果能重复选的话， 可以用goldgigger5这种思路。
</div></code></code></pre>
<h1 id="3-subset-sum-problem-dynamic-programming">3 Subset Sum Problem Dynamic Programming</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=s6FhG--P7z0&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=4">https://www.youtube.com/watch?v=s6FhG--P7z0&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=4</a></li>
</ul>
<p>本地和前面的背包问题相似，但有2点不同。</p>
<ul>
<li>不用管每个背包的重量属性</li>
<li>不是求value最大值, 而是value=target的组合是否存在</li>
</ul>
<p>例如 nums = [2,3,7,8,10] 可能的组合sum target</p>
<h1 id="31-dfs-top---bottom">3.1 DFS top -&gt; bottom</h1>
<p>略</p>
<h1 id="32-dp-bottom---top">3.2 DP bottom -&gt; top</h1>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp3.png" alt="dp3.png"></p>
<pre><code><code><div>if j &lt; input[i]:
    T[i][j] = T[i-1][j]
else:
    T[i][j] = T[i-1][j] or T[i-1][j - input[i]]
</div></code></code></pre>

    </body>
    </html>